/**
 * Created by Administrator on 2016/11/18.
 */
import jdk.internal.org.objectweb.asm.tree.analysis.Value;

import java.util.*;

import static java.util.Collections.swap;

public class Heap {
    private List<ValueIndex> heap=new List<ValueIndex>() {
        @Override
        public int size() {
            return 0;
        }

        @Override
        public boolean isEmpty() {
            return false;
        }

        @Override
        public boolean contains(Object o) {
            return false;
        }

        @Override
        public Iterator<ValueIndex> iterator() {
            return null;
        }

        @Override
        public Object[] toArray() {
            return new Object[0];
        }

        @Override
        public <T> T[] toArray(T[] a) {
            return null;
        }

        @Override
        public boolean add(ValueIndex valueIndex) {
            return false;
        }

        @Override
        public boolean remove(Object o) {
            return false;
        }

        @Override
        public boolean containsAll(Collection<?> c) {
            return false;
        }

        @Override
        public boolean addAll(Collection<? extends ValueIndex> c) {
            return false;
        }

        @Override
        public boolean addAll(int index, Collection<? extends ValueIndex> c) {
            return false;
        }

        @Override
        public boolean removeAll(Collection<?> c) {
            return false;
        }

        @Override
        public boolean retainAll(Collection<?> c) {
            return false;
        }

        @Override
        public void clear() {

        }

        @Override
        public ValueIndex get(int index) {
            return null;
        }

        @Override
        public ValueIndex set(int index, ValueIndex element) {
            return null;
        }

        @Override
        public void add(int index, ValueIndex element) {

        }

        @Override
        public ValueIndex remove(int index) {
            return null;
        }

        @Override
        public int indexOf(Object o) {
            return 0;
        }

        @Override
        public int lastIndexOf(Object o) {
            return 0;
        }

        @Override
        public ListIterator<ValueIndex> listIterator() {
            return null;
        }

        @Override
        public ListIterator<ValueIndex> listIterator(int index) {
            return null;
        }

        @Override
        public List<ValueIndex> subList(int fromIndex, int toIndex) {
            return null;
        }
    };
    int max;

    public Heap(int max) {
        this.max = max + 1;heap = new ArrayList<>();
    }

    public void insert(double value, int index) {
      if (heap.size() == 1)
           heap.add(new ValueIndex(0.0, 0));
        heap.add(new ValueIndex(value, index));
        heapUp(heap.size() - 1);
        if (heap.size() > max) {
            heap.remove(max);
        }
    }

    public int[] getValue() {
        int[] result = new int[max - 1];
        for (int i = 1; i < max; ++i) {
            result[i-1] = heap.get(i).index;
        }
        return result;
    }

    public void heapUp(int index) {
        if (index > 1) {
            int parent = index / 2;
            double parentValue = heap.get(parent).value;
            double indexValue = heap.get(index).value;
            if (parentValue < indexValue) {
                swap(heap, parent, index);
                heapUp(parent);
            }

        }
    }
}


class ValueIndex {
    public double value;
    public int index;

    public ValueIndex(double value, int index) {
        this.value = value;
        this.index = index;
    }
}
